package com.cjl.basicAlgorithm;



import java.util.*;

public class BasicAlgorithmPractice {
    /**
     * 167. 两数之和 II - 输入有序数组
     *
     * @param numbers
     * @param target
     * @return
     */
    public int[] twoSum(int[] numbers, int target) {
        // 定义左右指针
        int left = 0;
        int right = numbers.length - 1;
        // 从两端开始寻找合法的数字
        while (left < right) {
            if (numbers[left] + numbers[right] > target) { // 移动right
                right--;
            } else if (numbers[left] + numbers[right] < target) {
                left++;
            } else {
                break;
            }
        }
        return new int[]{left + 1, right + 1};
    }

    /**
     * 15. 三数之和
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        // 核心思路，固定一个数字，另外两个数相加为这个数的倒数
        List<List<Integer>> res = new ArrayList<>();
        // 对数组排序
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) { // 遍历第一个数
            int x = nums[i];
            // 跳过重复的数字
            if (i > 0 && x == nums[i - 1]) {
                continue;
            }
            // 双指针查找相应的j和k
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > 0) {
                    k--;
                } else if (s < 0) {
                    j++;
                } else {
                    res.add(List.of(x, nums[i], nums[k]));
                    // 跳过重复的j和k
                    while (j < k && nums[j] == nums[j + 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k - 1]) {
                        k--;
                    }
                    j++;
                    k--;
                }
            }
        }
        return res;
    }

    /**
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        // 对数组排序
        Arrays.sort(nums);
        int n = nums.length;
        int minDiff = Integer.MAX_VALUE;
        int res = 0;
        for (int i = 0; i < n - 2; i++) { // 遍历第一个数
            int x = nums[i];
            // 双指针查找相应的j和k
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                int s = x + nums[j] + nums[k];
                if (s > target) {
                    if (s - target < minDiff) {
                        // 更新最小差值
                        minDiff = s - target;
                        res = s;
                    }
                    k--;
                } else if (s < target) {
                    if (target - s < minDiff) {
                        minDiff = target - s;
                        res = s;
                    }
                    j++;
                } else {
                    return s;
                }
            }
        }
        return res;
    }

    /**
     * 18. 四数之和
     *
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        int len = nums.length;
        for (int i = 0; i < len - 3; i++) { // 枚举第一个数字
            long x = nums[i];
            // 跳过重复的数字
            if (i > 0 && x == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < len - 2; j++) {
                long y = nums[j];
                if (j > i + 1 && y == nums[j - 1]) {
                    continue;
                }
                int left = j + 1;
                int right = len - 1;
                while (left < right) {
                    long sum = x + y + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        res.add(List.of((int) x, (int) y, nums[left], nums[right]));
                        // 跳过重复数组
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return res;
    }

    /**
     * 2824.统计和小于目标的下标对数目
     *
     * @param nums
     * @param target
     * @return
     */
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int count = 0;
        int len = nums.size();
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int sum = nums.get(left) + nums.get(right);
            if (sum < target) {
                count += right - left;
                left++;
            } else {
                right--;
            }
        }
        return count;
    }

    /**
     * 611. 有效三角形的个数
     *
     * @param nums
     * @return
     */
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        int len = nums.length;
        for (int i = 2; i < len; i++) {
            int a = nums[i];
            int left = 0;
            int right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > a) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return count;
    }

    /**
     * 11. 盛最多水的容器
     *
     * @param height
     * @return
     */
    public int maxArea(int[] height) {
        int res = 0;
        int left = 0;
        int right = height.length - 1;
        // 不断获取最大接雨水面积
        while (left < right) {
            // 计算当前接雨水的面积
            int area = (right - left) * Math.min(height[left], height[right]);
            // 更新最大面积
            res = Math.max(res, area);
            // 移动短的一端指针
            if (height[left] > height[right]) {
                right--;
            } else {
                left++;
            }
        }
        return res;
    }

    /**
     * 42. 接雨水
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        // 创建两个数组分别表示每个位置之前和之后(包括自己的最大高度)
        int n = height.length;
        int[] pre_max = new int[n];
        pre_max[0] = height[0];
        for (int i = 1; i < n; i++) {
            pre_max[i] = Math.max(height[i], pre_max[i - 1]);
        }
        int[] suf_max = new int[n];
        suf_max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            suf_max[i] = Math.max(height[i], suf_max[i + 1]);
        }
        // 创建完两个数组之后利用两个数组求出每个柱子中的接水量
        int count = 0;
        for (int i = 0; i < n; i++) {
            // 当前格子的接水量
            int num = Math.min(pre_max[i], suf_max[i]) - height[i];
            count += num;
        }
        return count;
    }

    public int trap2(int[] height) {
        // 在计算过程中使用双指针计算当前的前缀和后缀最大值
        int res = 0;
        int n = height.length;
        int pre_max = 0;
        int suf_max = 0;
        int left = 0;
        int right = n - 1;
        while (left <= right) {
            // 先更新前缀和后缀最大值
            pre_max = Math.max(pre_max, height[left]);
            suf_max = Math.max(suf_max, height[right]);
            // 计算当前水量
            if (pre_max < suf_max) {
                res += pre_max - height[left];
                left++;
            } else {
                res += suf_max - height[right];
                right--;
            }
        }
        return res;
    }

    /**
     * 209. 长度最小的子数组
     *
     * @param target
     * @param nums
     * @return
     */
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int min = len + 1;
        int left = 0;
        int sum = 0;
        for (int right = 0; right < len; right++) {
            int num = nums[right];
            sum += num;
            // 如果此时总和大于target则更新最小长度，并判断减去left对应的值，判断是否合法
            while (sum >= target) {
                min = Math.min(min, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        // 如果长度没变则说明所有数的总和都小于target，直接返回0
        return min <= len ? min : 0;
    }

    /**
     * 713. 乘积小于 K 的子数组
     *
     * @param nums
     * @param k
     * @return
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        // 不存在乘积严格小于1的数
        if (k <= 1) {
            return 0;
        }
        int count = 0;
        int prod = 1;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            // 获得当前的累乘值
            int num = nums[right];
            prod *= num;
            // 如果累乘已经大于k则不断除去右端点的值
            while (prod >= k) {
                prod /= nums[left++];
            }
            count += right - left + 1;
        }
        return count;
    }

    /**
     * 3. 无重复字符的最长子串
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        char[] chars = s.toCharArray();
        int len = s.length();
        int res = 0;
        int left = 0;
        // 利用hash映射提升效率
        boolean[] contain = new boolean[128];
        for (int right = 0; right < len; right++) {
            char r = chars[right];
            // 如果存在则不断减去左端点的字符
            while (contain[r]) {
                char l = chars[left];
                contain[l] = false;
                left++;
            }
            // 此时一定无重复字符,则标记右端点字符对应元素
            contain[r] = true;
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    /**
     * 1004. 最大连续1的个数 III
     *
     * @param nums
     * @param k
     * @return
     */
    public int longestOnes(int[] nums, int k) {
        int res = 0;
        int count_0 = 0;
        int left = 0;
        for (int right = 0; right < nums.length; right++) {
            // 统计当前循环0的个数
            count_0 += 1 - nums[right];
            // 如果0的个数大于k则需要将left移动到使得个数小于等于k的位置
            while (count_0 > k) {
                count_0 -= 1 - nums[left++];
            }
            // 每次都统计合法的长度
            res = Math.max(res, right - left + 1);
        }
        return res;
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 定义虚拟头节点
        ListNode dummy = new ListNode(0, head);
        // 定义临时节点
        ListNode p0 = dummy;
        // temp移动到left前一个位置
        for (int i = 0; i < left - 1; i++) {
            p0 = p0.next;
        }
        ListNode pre = null;
        // cur为left的位置
        ListNode cur = p0.next;
        // 反转left到right的节点
        for (int i = 0; i < right - left + 1; i++) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        // 反转链表之后，cur是反转链表的下一个节点，pre是最后一个节点
        // 拼接链表
        p0.next.next = cur;
        p0.next = pre;
        return dummy.next;
    }

    /**
     * 25. K 个一组翻转链表
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        // 计算节点个数
        int count = 0;
        ListNode cur = head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        // 定义虚拟头节点
        ListNode dummy = new ListNode(0, head);
        // 定义临时节点
        ListNode p0 = dummy;
        // 用于修改cur指针指向，从而反转链表
        ListNode pre = null;
        // cur为left的位置
        cur = p0.next;
        // 只要剩余节点个数大于等于k就继续反转
        while (count >= k) {
            // 反转一次数量减k
            count -= k;
            // 反转k个节点
            for (int i = 0; i < k; i++) {
                // 保存cur.next节点
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
            // 拼接链表
            // 先保存p0.next
            ListNode next = p0.next;
            // 反转这一段
            next.next = cur;
            p0.next = pre;
            // 最后更新p0的位置
            p0 = next;
        }
        return dummy.next;
    }

    /**
     * 876. 链表的中间结点
     *
     * @param head
     * @return
     */
    public ListNode middleNode(ListNode head) {
        // 定义快慢指针
        ListNode slow = head;
        ListNode fast = head;
        // 循环条件为快指针不为空且快指针的next不为空
        while (fast != null && fast.next != null) {
            // 慢指针走一步，快指针走两步，则慢指针最终所在的位置一定是中间节点
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 141. 环形链表
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // 定义快慢指针，如果存在环，则快慢指针一定相遇
        ListNode slow = head;
        ListNode fast = head;
        // 如果步存在环则会退出循环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 如果存在环则快慢指针一定会相遇
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /**
     * 142. 环形链表 II
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        // 定义快慢指针，如果存在环，则快慢指针一定相遇
        ListNode slow = head;
        ListNode fast = head;
        // 如果步存在环则会退出循环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            // 如果快慢指针相遇，则说明有环
            if (slow == fast) {
                // 有环则慢指针和head持续移动，则一定会在入口处相遇
                while (slow != head) {
                    slow = slow.next;
                    head = head.next;
                }
                // 此时head和slow就是环的入口
                return head;
            }
        }
        return null;
    }

    /**
     * 206. 反转链表
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            // 保存之前的next
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 143. 重排链表
     *
     * @param head
     */
    public void reorderList(ListNode head) {
        // 先找到链表的中间节点
        ListNode midNode = middleNode(head);
        // 反转mid链表
        ListNode head2 = reverseList(midNode);
        // 只要head2.next不为空则持续循环
        while (head2.next != null) {
            // 先保存两个head的next
            ListNode next = head.next;
            ListNode next2 = head2.next;
            // 转换
            head.next = head2;
            head2.next = next;
            // 修改两个head的位置
            head = next;
            head2 = next2;
        }
    }

    /**
     * 237. 删除链表中的节点
     *
     * @param node
     */
    public void deleteNode(ListNode node) {
        // 复制下一个节点的值到这个节点
        node.val = node.next.val;
        // 删除下一个节点即可
        node.next = node.next.next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     *
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 定义虚拟头节点
        ListNode dummy = new ListNode(-1, head);
        // 定义左右指针
        ListNode left = dummy, right = dummy;
        // 右指针移动n步
        for (int i = 0; i < n; i++) {
            right = right.next;
        }
        // 同时移动左右指针保证两指针的距离始终为n，当右指针到达末尾时，左指针就指向要删除的元素的前一个元素
        while (right.next != null) {
            // 左右指针一起移动
            left = left.next;
            right = right.next;
        }
        // 此时删除待删除节点
        left.next = left.next.next;
        return dummy.next;
    }

    // 常规方法
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        // 定义虚拟头节点
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        int nodeNum = 0;
        // 求当前链表长度
        while (cur.next != null) {
            cur = cur.next;
            nodeNum++;
        }
        // 找到待删除节点的前一个节点
        int deleteNum = nodeNum - n;
        // 归位cur
        cur = dummy;
        while (deleteNum-- > 0) {
            cur = cur.next;
        }
        // 删除
        cur.next = cur.next.next;
        return dummy.next;
    }

    /**
     * 83. 删除排序链表中的重复元素
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {
        // 判断head是否为空
        if (head == null) {
            return head;
        }
        ListNode cur = head;
        while (cur.next != null) {
            // 如果当前节点的值和下一个节点的值相同则删除下一个节点
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                // 如果不等与cur后移
                cur = cur.next;
            }
        }
        return head;
    }

    /**
     * 82. 删除排序链表中的重复元素 II
     *
     * @param head
     * @return
     */
    public ListNode deleteDuplicates2(ListNode head) {
        // 由于头节点有可能被删除，所以需要虚拟头节点
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            // 判断下一个节点和下下个节点是否相同
            // 将cur.next.val保存起来，方便后续判断
            int temp = cur.next.val;
            if (temp == cur.next.next.val) {
                // 相同则循环删除
                while (cur.next != null && cur.next.val == temp) {
                    // 删除后一个节点
                    cur.next = cur.next.next;
                }
            } else {
                // 不相同则跳过这个节点
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    /**
     * 203. 移除链表元素
     *
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        // 非空判断
        if (head == null) return null;
        // 定义虚拟头节点和cur
        ListNode dummy = new ListNode(-1, head), cur = dummy;
        // 循环删除
        while (cur.next != null) {
            if (cur.next.val == val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }

    /**
     * 104. 二叉树的最大深度
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        // 递归终止条件，遇到null则返回0
        if (root == null) {
            return 0;
        }
        // 递归遍历左右子树，取最大值
        int leftDepth = maxDepth(root.left);
        int rightDepth = maxDepth(root.right);
        // 返回最大值 + 1,也就是加上本层的高度
        return Math.max(leftDepth, rightDepth) + 1;
    }

    /**
     * 111. 二叉树的最小深度
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        // 递归终止条件，遇到null则返回0
        // 此时上一层就是叶子节点，可以接受结果了
        if (root == null) {
            return 0;
        }
        // 由于null不可算作叶子节点，如果左子树为null，就递归右子树寻找叶子节点
        if (root.left == null) {
            return minDepth(root.right) + 1;
        }
        if (root.right == null) {
            return minDepth(root.left) + 1;
        }
        // 返回左右子树的深度小的那一个，则取最小值
        return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
    }

    public int minDepth2(TreeNode root) {
        // 递归终止条件，遇到null则返回0
        // 此时上一层就是叶子节点，可以接受结果了
        if (root == null) {
            return 0;
        }
        int leftDepth = minDepth(root.right) + 1;
        int rightDepth = minDepth(root.left) + 1;
        // 由于null不可算作叶子节点，如果左子树为null，就递归右子树寻找叶子节点
        if (root.left == null) {
            return leftDepth;
        }
        if (root.right == null) {
            return rightDepth;
        }
        // 返回左右子树的深度小的那一个，则取最小值
        return Math.min(leftDepth, rightDepth);
    }

    /**
     * 112. 路径总和
     *
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        targetSum -= root.val;
        if (root.left == null && root.right == null) {
            return targetSum == 0;
        }
        if (root.left != null) {
            boolean flag = hasPathSum(root.left, targetSum);
            if (flag) {
                return true;
            }
        }
        if (root.right != null) {
            boolean flag = hasPathSum(root.right, targetSum);
            if (flag) {
                return true;
            }
        }
        return false;
    }

    /**
     * 100. 相同的树
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 递归到根节点时就返回true
        if (p == null && q == null) {
            return true;
        }
        // 左右子树其中一颗为空则返回false
        if (p == null || q == null) {
            return false;
        }
        // 节点值不相同返回false
        if (p.val != q.val) {
            return false;
        }
        // 递归判断左子树和右子树是否均相同
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

    /**
     * 101. 对称二叉树
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        return isSameTree2(root.left, root.right);
    }

    public boolean isSameTree2(TreeNode p, TreeNode q) {
        // 递归到根节点时就返回true
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        // 判断是否对称，那么就判断左边的左子树是否等于右边的右子树，以及左边的右子树是否等于右边的左子树
        return isSameTree2(p.left, q.right) && isSameTree2(p.right, q.left);
    }

    /**
     * 110. 平衡二叉树
     *
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        // 判断结果是不是非-1，
        return getHeight(root) != -1;
    }

    // 获取二叉树的深度，如果不平衡则返回-1
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 递归搜索左子树的深度
        int leftHeight = getHeight(root.left);
        // 如果左子树返回的是-1则左子树已经不平衡，直接向上返回-1即可
        if (leftHeight == -1) return -1;
        // 右子树同理
        int rightHeight = getHeight(root.right);
        if (rightHeight == -1) return -1;
        // 此时左右子树返回的不是-1，则判断其高度差是否大于1，若大于1，则从这个节点开始不平衡，返回-1
        if (Math.abs(leftHeight - rightHeight) > 1) return -1;
        // 此时返回正常高度
        return Math.max(leftHeight, rightHeight) + 1;
    }

    /**
     * 199. 二叉树的右视图
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        // 结果集
        ArrayList<Integer> res = new ArrayList<>();
        // 深度优先遍历
        rightSideViewDFS(root, 0, res);
        // 返回结果集
        return res;
    }

    private void rightSideViewDFS(TreeNode root, int depth, ArrayList<Integer> res) {
        // 遇到空节点就返回
        if (root == null) {
            return;
        }
        // 如果递归深度 == 结果集长度，就添加当前元素
        if (depth == res.size()) {
            res.add(root.val);
        }
        // 先遍历右子树，再遍历左子树
        rightSideViewDFS(root.right, depth + 1, res);
        rightSideViewDFS(root.left, depth + 1, res);
    }

    /**
     * 226. 翻转二叉树
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        return root;
    }

    /**
     * 1026. 节点与其祖先之间的最大差值
     *
     * @param root
     * @return
     */
    private int ans;

    public int maxAncestorDiff(TreeNode root) {
        maxAncestorDiffDFS(root, root.val, root.val);
        return ans;
    }

    private void maxAncestorDiffDFS(TreeNode node, int min, int max) {
        if (node == null) {
            // 优化，再这里更新答案
            ans = Math.max(ans, max - min);
            return;
        }
        // 更新min和max,其中 min <= node.val <= max.val
        min = Math.min(min, node.val);
        max = Math.max(max, node.val);
        // 更新答案
        // ans = Math.max(ans, Math.max(node.val - min, max - node.val));
        maxAncestorDiffDFS(node.left, min, max);
        maxAncestorDiffDFS(node.right, min, max);
    }

    /**
     * 98. 验证二叉搜索树
     * @param root
     * @return
     */
    public boolean isValidBST(TreeNode root) {
        // 根节点传递的区间为(-∞,+∞)
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBST(TreeNode root, long left, long right) {
        // 递归终止条件，当递归到空节点时则返回true
        if (root == null) {
            return true;
        }
        // 前序遍历，判断当前这个节点是否在合法的区间范围之内
        int x = root.val;
        // 判断当前节点是否在合法区间内
        boolean flag = left < x && right > x;
        // 判断左子树的合法性
        boolean leftFlag = isValidBST(root.left, left, x);
        // 判断右子树的合法性
        boolean rightFlag = isValidBST(root.right, x, right);
        // 最后返回当前节点和左右子树的合法性与运算
        return flag && leftFlag && rightFlag;
    }

    /**
     * 236. 二叉树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 如果当前节点是空，或者是p或q其中任意一个，则递归终止，直接返回当前节点
        if (root == null || root == p || root == q) {
            return root;
        }
        // 此时可以确定当前节点不是p也不是q，也不是null，则递归左右子树继续寻找
        TreeNode left = lowestCommonAncestor(root.left, q, p);
        TreeNode right = lowestCommonAncestor(root.right, q, p);
        // 如果左子树和右子树均找到节点了，则当前的root就是最近的公共祖先，直接返回
        if (left != null && right != null) {
            return root;
        }
        // 此时左子子树不可能都有值
        // 如果左子树找则返回左子树，右子树找到了则返回右子树，都没找到则返回null
        // 代码可以简化为以下形式
        // 左子树不为空则返回左子树，否则直接返回右子树（包含了右子树不为空和都没找到两种情况）
        return left != null ? left : right;
    }

    /**
     * 235. 二叉搜索树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        // 利用二叉搜索树的特性，如果当前节点在区间[p,q]之间则当前元素就是最近公共祖先
        // 获取当前节点值
        int x = root.val;
        // 如果p，q均小于root.val，则公共祖先在左子树
        if (q.val < x && p.val < x) {
            return lowestCommonAncestor2(root.left, q, p);
        }
        // 如果p，q均大于root.val，则公共祖先在右子树中
        if (q.val > x && p.val > x) {
            return lowestCommonAncestor2(root.right, p, q);
        }
        // 此时p，q在root的两侧，root就是公共祖先
        return root;
    }

    /**
     * 102. 二叉树的层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        // 先判断是否为空数组
        if (root == null) return List.of();
        ArrayList<List<Integer>> res = new ArrayList<>();
        ArrayList<TreeNode> cur = new ArrayList<>();
        cur.add(root);
        while (!cur.isEmpty()) {
            ArrayList<TreeNode> next = new ArrayList<>();
            ArrayList<Integer> vals = new ArrayList<>();
            for (TreeNode node : cur) {
                vals.add(node.val);
                if (node.left != null) {
                    next.add(node.left);
                }
                if (node.right != null) {
                    next.add(node.right);
                }
            }
            cur = next;
            res.add(vals);
        }
        return res;
    }

    public List<List<Integer>> levelOrder2(TreeNode root) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        // 先判断是否为空数组
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            res.add(list);
        }
        return res;
    }

    /**
     * 103. 二叉树的锯齿形层序遍历
     * @param root
     * @return
     */
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<List<Integer>> res = new ArrayList<>();
        // 先判断是否为空数组
        if (root == null) return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean isReverse = true;
        while (!queue.isEmpty()) {
            ArrayList<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            if (isReverse) {
                Collections.reverse(list);
            }
            isReverse = !isReverse;
            res.add(list);
        }
        return res;
    }

    /**
     * 513. 找树左下角的值
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        TreeNode node = root;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            node = queue.poll();
            // 右孩子先入队，左孩子再入队
            if (node.right != null) {
                queue.add(node.right);
            }
            if (node.left != null) {
                queue.add(node.left);
            }
        }
        return node.val;
    }

    private static final String[] MAPPING = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        ArrayList<String> res = new ArrayList<>();
        if (digits.length() == 0) {
            return res;
        }
        char[] digitsArr = digits.toCharArray();
        char[] path = new char[digits.length()];
        dfs(0,digitsArr,path,res);
        return res;
    }

    private void dfs(int i, char[] digitsArr, char[] path, ArrayList<String> res) {
        if (i == digitsArr.length) {
            res.add(new String(path));
            return;
        }
        char[] chars = MAPPING[digitsArr[i] - '0'].toCharArray();
        for (char c : chars) {
            path[i] = c;
            dfs(i + 1, digitsArr, path, res);
        }
    }


}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}




class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}